package algorithms.a03sortadvance;

import java.util.Arrays;

/**
 * 归并排序 计算逆序对
 *
 * @author 王昊然
 * @create 2018-02-06 11:39
 **/
public class MergeSortCalTheReverse {

    /**
     * 自顶向下的归并排序
     *
     * @param arr
     * @date: 2018/2/6 16:10
     * @author: 王昊然
     */
    public static int calAuxArray(Comparable[] arr) {
        int n = arr.length;
        int reserveCount = 0;
        reserveCount = mergeSort(arr, 0, n - 1);//参数是下标
        return reserveCount;
    }

    private static int mergeSort(Comparable[] arr, int left, int right) {

        if (left >= right) {
            return 0;
        }

        int middle = (right + left) / 2;
        int count1 = mergeSort(arr, left, middle);//参数是下标
        int count2 = mergeSort(arr, middle + 1, right);

        if (arr[middle].compareTo(arr[middle + 1]) < 0)
            return count1+count2;//如果中间左侧的已经比右侧小，说明已经是一个排好序的数组片段，不需要再归并

        int count3 = mergeByTwoOrdererParts(arr, left, middle, right);
        return count1 + count2 + count3;
    }

    /**
     * 二分后，两部分各自都已经是排序好的数组情况下，整体进行合并
     * 注意，middle并不一定非要代表中间的下标，只要理解为两个数组段的连接位置即可，特别在由下到上的归并中
     *
     * @param arr
     * @param left
     * @param middle
     * @param right
     */
    private static int mergeByTwoOrdererParts(Comparable[] arr, int left, int middle, int right) {

        int reserveCount = 0;

        Comparable[] arrClone = Arrays.copyOfRange(arr, left, right + 1);
        int i = 0;
        middle = middle - left;//转为clone数组的中间位置下标
        int j = middle + 1;

        for (int k = left; k <= right; k++) {

            if (i > middle) {
                arr[k] = arrClone[j];
                j++;
            } else if (j > arrClone.length - 1) {
                arr[k] = arrClone[i];
                i++;

            } else if (arrClone[i].compareTo(arrClone[j]) <= 0) {
                arr[k] = arrClone[i];
                i++;
            } else {
                arr[k] = arrClone[j];
                j++;
                reserveCount += middle - i + 1;
            }
        }

        return reserveCount;
    }


    public static void main(String[] args) {
        //int N = 13000;
        //Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 300000); //1排序数组数值范围小，插入排序优势明显
        Integer[] arr = new Integer[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println(MergeSortCalTheReverse.calAuxArray(arr));

    }

}
